package medium

/*
时间复杂度:O(N) N是s2的长度
空间复杂度:O(C) C是字母集

解:针对两个数组,如果长度一样且数组内元素一样,则两个数组一样(数组可比较,切片不能比较)
*/

func checkInclusion(s1 string, s2 string) bool {
	n, m := len(s1), len(s2)
	if n > m {
		return false
	}
	// 如果s2中包含s1的排列,则s2中一定存在一个长度为len(s1)的窗口,里面出现的所有字母及其数量与s1相等
	// 所以初始化一个长度为len(s1)的窗口,并计算该窗口内出现的所有字母及其数量
	var cnt1, cnt2 [26]int
	for i, s := range s1 {
		cnt1[s-'a']++
		cnt2[s2[i]-'a']++
	}

	if cnt1 == cnt2 {
		return true
	}

	// 滑动窗口
	for i := n; i < m; i++ {
		cnt2[s2[i]-'a']++
		cnt2[s2[i-n]-'a']--
		if cnt1 == cnt2 {
			return true
		}
	}
	return false
}